Laplacian matrix

Laplacian, Spectral graph theory, Supra Laplacian matrix

• https://en.wikipedia.org/wiki/Laplacian_matrix

Definition

The basic Laplacian matrix (combinatorial Laplacian matrix) is defined as:

$$L = D - A$$

or

$$L_{i,j}:= \begin{cases} \deg(v_i) & \mbox{if}\ i = j \\ -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise} \end{cases}$$

Intuition

This can be understood as a discrete version of the Laplacian operator defined for Euclidean space. Note that the sign is the opposite. Laplacian operator produces a negative value for “peaks” whereas the graph Laplacian produces a positive value.

A discrete version of derivative can be thought as a simple difference. Then the divergence can be thought as another difference between those differences. For instance, imagine a chain of node $i, j, k$ and a scalar function defined for each node with value $x_i$. If we imagine them as three adjacent points in 1D space, the first derivative can be approximated as $x_k - x_j$ and $x_j - x_i$. The second derivative can be $x_k - x_j - x_j + x_i = x_k + x_i - 2x_j$. If we change the sign, $2x_j - x_i - x_k$, then we can the same thing as the graph Laplacian.

More explanations

• quora: What’s the intuition behind a Laplacian matrix?
• mathoverflow: Intuitively, what does a graph Laplacian represent?
• https://csustan.csustan.edu/~tom/Clustering/GraphLaplacian-tutorial.pdf